/**
 * 功能：bloom filter算法实现
 */
package frontier;

import java.util.BitSet;

public class BloomFilter implements VisitedUrl {

	private static final int BITSET_SIZE = 2 << 24;// 定义位数
	private static final int[] seeds = new int[] { 7, 11, 13, 31, 37, 61 };// 随机种子
	private static BitSet bits = new BitSet(BITSET_SIZE);
	private SimpleHash[] func = new SimpleHash[seeds.length];

	public BloomFilter() {
		for (int i = 0; i < seeds.length; i++) {
			func[i] = new SimpleHash(BITSET_SIZE, seeds[i]);
		}
	}

	public void add(String url) {
		for (SimpleHash f : func) {
			bits.set(f.hash(url), true);
		}
	}

	public  boolean contains(String value) {
		if (value == null)
			return false;
		boolean ret = true;
		for (SimpleHash f : func)
			// 这里其实没必要全部跑完，只要一次ret==false那么就不包含这个字符串
			ret = ret && bits.get(f.hash(value));
		return ret;
	}

	public static class SimpleHash {
		private int cap;
		private int seed;

		public SimpleHash(int cap, int seed) {
			this.cap = cap;
			this.seed = seed;
		}

		public int hash(String value) {
			int result = 0;
			int len = value.length();
			for (int i = 0; i < len; i++) {
				result = seed * result + value.charAt(i);
			}
			return (cap - 1) & result;
		}
	}
	
	//test 
	public static void main(String [] args) {
		String value = "http://www.rw.uestc.edu.cn/teachers_construct/teacher_personal_page.aspx?teacherName=%e9%92%9f%e6%af%85&id=73#";
		BloomFilter filter = new BloomFilter();
		System.out.println(filter.contains(value));
		filter.add(value);
		System.out.println(filter.contains(value));
	}
}
